1. Field of the Invention
The present invention relates to digital packet transmissions, and particularly to a method and system for providing congestion control in a digitally switched packet communication network employing serial data transmission.
2. Description of the Invention
Traditional congestion control schemes are used to minimize the switch buffer requirements and enable users to have fair access to the available bandwidth. In particular, the congestion control serves to reduce the load on the network when the load becomes excessive and the packets become lost. Hence, the congestion control allows the network to recover from congestion and operate at an optimum load. Due to scalability issues, congestion control is usually implemented end-to-end, i.e., Internet source nodes performs congestion control dynamically based on the congestion status of the network.
In most Internet applications, a typical congestion control employs increase-decrease response functions to adjust the sending rate based on a binary congestion feedback and available bandwidth in the network. If the feedback information indicates that the capacity of the bottleneck link has been exceeded in the network, the congestion control applies the decrease function (fD) to the current sending rate. Otherwise, the congestion control applies the increase function (fI) to the current sending rate. In this scheme, the network load is kept at an optimal capacity by limiting the load on the network by properly adjusting the sending rates.
The following equation summarizes the increase-decrease congestion control schemes:
                              x                      i            +            1                          =                  {                                                                                                                x                      i                                        -                                                                  f                        D                                            ⁡                                              (                                                  x                          i                                                )                                                                              ,                                      f                    >                    0                                                                                                                                                                  x                      i                                        +                                                                  f                        I                                            ⁡                                              (                                                  x                          i                                                )                                                                              ,                                      f                    =                    0.                                                                                                          (        1        )            
The above equation (1) uses these symbols:
f=congestion feedback signal, wherein f is positive if congestion is present; otherwise, f is zero (in practice packet loss is typically used as feedback f);
xi=current sending rate during cycle i, wherein the adjustment to the sending rate is made once per congestion control cycle, and a typical congestion control cycle length is one round-trip time (RTT);
xi+1=next sending rate of data;
fD=decrease function to the current sending rate; and,
fI=increase function to the current sending rate.
A prior art known as AIMD (Additive-Increase/Multiplicative-Decrease) scheme has both fI and fD as linear functions of the current rate xi. The AIMD method is typically used in a TCP environment and defined as:
                    {                                                                                                  f                    D                                    ⁡                                      (                    x                    )                                                  =                                  β                  ⁢                                                                          ⁢                  x                                                                                                                                              f                    I                                    ⁡                                      (                    x                    )                                                  =                                  α                  .                                                                                        (        2        )            
From the above equation (2), it can be inferred that the decrease step (fD) in the AIMD method is multiplicative (or linear function by a factor for each RTT) and the increase step (fI) is additive (or constant function for each RTT). The recommended value for β and α is 0.5 and 1, respectively.
Another enhanced increase-decrease algorithm in the prior art, known as the binomial algorithms, is an extension of the above AIMD concept and defined as follows:
                    {                                                                                                  f                    D                                    ⁡                                      (                    x                    )                                                  =                                  β                  ⁢                                                                          ⁢                                      x                    l                                                                                                                                                                f                    I                                    ⁡                                      (                    x                    )                                                  =                                  α                  ⁢                                                                          ⁢                                                            x                                              -                        k                                                              .                                                                                                          (        3        )            
In practice, however, this binomial algorithm cannot be used for l>1, as the decrease step may result in a reduction of the sending rate to a negative value from any arbitrary state xi. As a result, the use of the conventional binomial algorithms has been limited for the value of l≦1, and the recommended values of l and k have been limited to satisfy the condition of k+l=1. Special cases of binomial congestion control schemes above, known as the IIAD (Inverse Increase Additive Decrease) method, recommends setting k=1 and l=0, and another SQRT (Square Root) method recommends setting k=l=0.5. Furthermore, in all binomial schemes, k+l must be strictly above zero to converge to a fair state (i.e., fair link utilization). For background information, see for example, “Binomial Congestion Control Algorithms,” IEEE InfoCom 2001, the content of which is hereby incorporated by reference.
Although there are different types of congestion control schemes available as stated above, no existing techniques are available that can effectively control the data flow between source and destination end systems such that congestion is controlled and the unused capacity is utilized while maintaining certain quality-of-service (QoS) guarantees. Accordingly, the present invention proposes a non-linear increase-decrease congestion control method using real-time estimates of the bottleneck bandwidth to achieve high flow scalability and maintain steady packet loss, which does not grow with an increase in the number of data flows sharing a common link.